'''
字符串查找
'''

#BM 算法 https://time.geekbang.org/column/article/71525


SIZE = 256
def generateBC(pattern: str, bc):
    for i in range(len(pattern)):
        bc[ord(pattern[i])] = i

def bm(s:str, pattern: str):
    bc = [-1] * SIZE  # 记录模式字符串中每个字符最后出现的位置
    generateBC(pattern, bc)  # 构建坏字符哈希表
    i = 0 # 表示主串和模式串对齐的第一个字符
    while i < len(str) - len(pattern):
        # 模式串从后到前匹配
        j = len(pattern) - 1
        while j >= 0:
            if s[i+j] != pattern[j]:
                break
            j -= 1
        if j < 0:
            return i # 匹配成功， 返回主串与模式串第一个匹配的字符的位置
        i = i + (j - bc[s[i+j]])  # 这里等同于将模式串往后滑动j - bc[a[i+j]]位

    return -1

    